#include "tree_2_4.h"


Node::Node ( InnerNode *parent , Tree_2_4 *tree, bool isLeaf)
{
	this->parent = parent;
	this->tree = tree;
	this->isLeaf = isLeaf;
}

bool Node::Has(int studentId)
{
	int i;

	for ( i = 0; i < count; i++ )
	{
		if ( studentIds[i] == studentId )
		{
			return true;
		}
	}

	return false;
}

int Node::Find ( int studentId )
{
	int i;

	for ( i = 0; i < count; i++ )
	{
		if ( studentIds[i] == studentId )
		{
			return i;
		}
	}

	return NOTFOUND;
}

int Node::Find ( Object *object )
{
	int i;

	for ( i = 0; i < this->count; i++ )
	{
		if ( pointers[i] == object)
		{
			return i;
		}
	}

	return NOTFOUND;
}

Object *Node::GetPointer ( int studentId )
{
	int i;

	if ( studentId <= studentIds[0] )
	{
			return pointers[0];
	}
	else
	{
		for ( i = 0; i < count - 1; i++ )
		{
			if ( studentId > studentIds[i] && studentId <= studentIds[i + 1] )
			{
				return pointers[i + 1];
			}
		}
	}

	return NULL;
}

int Node::GetPointer ( Object *object )
{
	int i;

	for ( i = 0; i < count; i++ )
	{
		if ( object == pointers[i])
		{
			return i;
		}
	}

	return NOTFOUND;
}

bool Node::SiblingCanGive ( void )
{
	Node *sibling = GetSibling();

	return sibling->count > 2;
}

Node *Node::GetSibling ( void )
{
	InnerNode *parent = ( InnerNode * ) this->parent;
	int position = parent->GetPointer ( this );

	if ( position == parent->Count() - 1 )
	{
		return ( Node * ) parent->pointers [ position - 1 ];
	}
	else
	{
		return ( Node * ) parent->pointers [ position + 1 ];
	}

}

void Node::TakeFromSibling ( int studentId )
{
	int i, j;
	Node *sibling = GetSibling();	

	/* ........ ... .......... ......... ... .......
	 *... ....., .. .......... .........
	 */

	for ( i = 0; i < count; i++ )
	{
		if ( sibling->studentIds[0] < studentIds[i] )
		{
			for ( j = count; j > i; j-- )
			{
				studentIds [ j ] = studentIds [ j - 1 ];
				pointers [ j ] = pointers [ j - 1];
			}

			studentIds [ i ] = sibling->studentIds [ 0 ];
			pointers [ i ] = sibling->pointers [ 0 ];
			count++;

			break;
		}
	}

	if ( i == count )
	{
		studentIds[count] = sibling->studentIds [ 0 ];
		pointers [ count ] = sibling->pointers [ 0 ];
		count++;
	}

	/* ........ ... .......... ........., .. .....
	 *.... . ....... ....
	 */
		
	sibling->pointers[0] = NULL;

	i = 0;

	while ( i < count - 1 )
	{
		sibling->studentIds [i] = sibling->studentIds [ i + 1 ];
		sibling->pointers [i] = sibling->pointers [ i + 1 ];
		
		i++;
	}
		
	sibling->count--;
	sibling->pointers[ sibling->count ] = NULL;

	/* ........ ... .......... ...... .... . ...... ....
	 *3 ........ ...... .. ........... . .......... ... .....
	 *..........
	 */

	int position = this->Find ( studentId );

	/* .......... .... ... ......... ... ..... ....
	 *.. ........ .... ........ ... .... ........,
	 *.... .. ......... .. .........
	 */

	i = position;

	while ( i < count - 1 )
	{
		studentIds [i] = studentIds [ i + 1 ];
		pointers [i] = pointers [ i + 1 ];

		i++;
	}
		
	count--;
	pointers[ count ] = NULL;

	if ( this->HasParent() )
	{
		parent->UpdateSeparator ( this, this->Max() );
	}

}

void Node::Merge ( int studentId )
{
	Node *sibling = GetSibling(), *nodeToDelete, *destinationNode;
	int i, j, k, idToDelete;

	this->Max() < sibling->Max() ? idToDelete = this->Max() : idToDelete = sibling->Max();

	this->Has ( idToDelete ) ? nodeToDelete = this : nodeToDelete= sibling;
	nodeToDelete == this ? destinationNode = sibling : destinationNode = this;

	for ( i = 0; i < nodeToDelete->count; i++ )
	{
		for ( j = 0; j < destinationNode->count; j++ )
		{
			if ( nodeToDelete->studentIds[i] < destinationNode->studentIds[j] )
			{
				for ( k = destinationNode->count; k > j; k-- )
				{
					destinationNode->studentIds [ k ] = destinationNode->studentIds [ k -1 ];
					destinationNode->pointers [ k ] = destinationNode->pointers [ k - 1];
				}

				destinationNode->studentIds [ j ] = nodeToDelete->studentIds [ i ];
				destinationNode->pointers [ j ] = nodeToDelete->pointers [ i ];
				nodeToDelete->pointers [ i ] = NULL;
				destinationNode->count++;

				break;
			}
		}
	}

	/* .. ..... ..... ......... .... ....... next .... .. ..........
	 *..... . ....... ... ....... ...... .. ..... .......... ......,
	 *......... .. ...... ... ... ..... ..... .... . ...... .....
	 */

	if ( this->IsLeaf() )
	{
		Leaf *previous = tree->GetPrevious ( (Leaf *) nodeToDelete );

		if ( previous == NULL )
		{
			tree->firstLeaf = (Leaf *) destinationNode;
		}
		else
		{
			previous->SetNext ( ( Leaf * ) destinationNode );
		}
	}
	else
	{
		( ( InnerNode * ) destinationNode )->UpdateChildrenParent();
	}

	/* ........ ... studentId. */
	i = destinationNode->Find ( studentId );

	while ( i < destinationNode->count - 1 )
	{
		destinationNode->studentIds [i] = destinationNode->studentIds [ i + 1 ];
		destinationNode->pointers [i] = destinationNode->pointers [ i + 1 ];

		i++;
	}
		
	destinationNode->count--;
	destinationNode->pointers[ destinationNode->count ] = NULL;

	( ( InnerNode *) destinationNode->parent )->Delete ( idToDelete );
}

void Node::Delete ( int studentId )
{
	if ( count == 2 && SiblingCanGive() )
	{
		/* .. ... ...... .. ...... .. ..... .. ......... ........
		 *... . ....... .. ...... .. ... .....,
		 *...... .. ......... ........ ... ....... ... ... 
		 *... ........ ......... .. studentId.
		 */

		this->TakeFromSibling ( studentId );
	}
	else if ( count == 2 && !SiblingCanGive() )
	{
		/* .. ... ...... .. ......... .. ........ ... .. ..... ..... 
		 *.... .. ............ . ....... ... ... .... ...... .... 
		 *........... ... ........ ... ... ...... . ....... ... ..
		 *... ..... ........ ... ... .... ....
		 *............ .. ... ...... ....
		 */

		this->Merge ( studentId );
	}
	else
	{
		/* ......... ... ......... ..... .. ...... ......
		 *.... .... ... ....... .... ..... .... ........
		 */

		int position = this->Find ( studentId );

		/* .. . ...... ..... ....., ........ ... .....
		 *.. .. ........ ... ........... ... ........
		 *.... .........
		 */

		//TO DO: destructor ... .. ....... ... .. ......... .. ..... ^^

		/* .......... .... ... ......... ... ..... ....
		 *.. ........ .... ........ ... .... ........,
		 *.... .. ......... .. .........
		 */

		int i = position;

		while ( i < count - 1 )
		{
			studentIds [i] = studentIds [ i + 1 ];
			pointers [i] = pointers [ i + 1 ];

			i++;
		}
		
		count--;
		pointers[ count ] = NULL;

		if ( position == count && this->HasParent() )
		{
			InnerNode *parent = ( InnerNode * ) this->parent;
			parent->UpdateSeparator ( this, this->Max() );
		}
	}
}

